#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include "AVL.h"

struct  node
{
    int element;
    AVL left_son;
    AVL right_son;
    int height;
};

int getheight(position p);
int Height(position p);
static position  DoubleRoateWithright(position K3);
static position  DoubleRoateWithLeft(position K3);
static position  singleRoateWithRight(position K2);
static position  singleRoateWithLeft(position K2);

AVL insert(int need_element, AVL a_t)
{
    if(a_t == NULL)
    {
        a_t = (AVL)malloc(sizeof(node));
        a_t->element = need_element;
        a_t->left_son = NULL;
        a_t->right_son = NULL;
        a_t->height = 0;
    }
    else
    {
        if(need_element < a_t->element)
        {
            a_t->left_son= insert(need_element, a_t->left_son);
            if(Height(a_t->left_son) - Height(a_t->right_son) == 2)
            {
                if(need_element < a_t->left_son->element)
                    a_t = singleRoateWithLeft(a_t);
                else
                    a_t = DoubleRoateWithLeft(a_t);
            } 
        }
        if(need_element > a_t->element)
        {
            a_t->right_son = insert(need_element, a_t->right_son);
            if(Height(a_t->right_son)-Height(a_t->left_son) == 2)
            {
                if(need_element > a_t->right_son->element)
                    a_t = singleRoateWithRight(a_t);
                else
                    a_t = DoubleRoateWithright(a_t);
            } 
        }       
        a_t->height = getheight(a_t);
    }
    return a_t;
}

static position singleRoateWithLeft(position K2)
{
    position K1;
    K1 = K2->left_son;
    K2->left_son = K1->right_son;
    K1->right_son = K2;
    K2->height = getheight(K2);
    K1->height = getheight(K1);
    return K1;
}

static position  singleRoateWithRight(position K2)
{
    position K1;
    K1 = K2 -> right_son;
    K2 -> right_son = K1 -> left_son;
    K1-> left_son = K2;
    K2->height = getheight(K2);
    K1->height = getheight(K1);
    return K1;
}

static position DoubleRoateWithLeft(position K3)
{
    position K1;
    position K2;
    K2 = K3->left_son; 
    K1 = K2->right_son;
    K3->left_son = singleRoateWithRight(K2);

    singleRoateWithLeft(K3);
    K2->height = getheight(K2);
    K1->height = getheight(K1);
    K3->height = getheight(K3);
    return K1;
}

static position DoubleRoateWithright(position K3)
{
    position K2;
    position K1;
    K2 = K3->right_son;
    K1 = K2->left_son;
    K3->right_son = singleRoateWithLeft(K2);
    singleRoateWithRight(K3);
    K2->height = getheight(K2);
    K1->height = getheight(K1);
    K3->height = getheight(K3);
    return K1;
}
int getheight(position p)
{
    return std::max(Height(p->left_son), Height(p->right_son)) + 1;
}
int Height(position p)
{
    if(p == NULL)
        return -1;
    return p->height;
}
void print(AVL b_t)
{
    if(b_t == NULL)
    {
       printf("AVL is NULL\n");
       return; 
    }
        
    position p = b_t;
    if(p->left_son != NULL)
    {
        print(p->left_son);
    }
    for (int i = 0; i < p-> height; ++i)
    {
        printf(" ");
    }
    printf("%d\n", p->element);
    
    if(p->right_son != NULL)
    {
        print(p->right_son);
    }
        
}
